The following paragraphs give definitions of terms used throughout this document.
Physical Link: a single point-to-point (PPP) serial transmission link between two nodes in the network (such as between two routers or between a router and a host machine). The implementation of a serial link may take various forms such as an optical fiber a wavelength segment on an optical fiber among others.
Physical output port: the output port of the router that supports one physical link.
Logical link: A point-to-point traffic path between two routers that is composed of multiple parallel physical links and appears from a routing point of view to be one link.
Logical output port: the collection of physical output ports that support the physical links of a logical link.
Data traffic unit: a portion of the original traffic stream. This may be a complete packet such as an IP data packet, a part of a packet, a collection of packets or an arbitrary number of bytes from the total stream.
Supertrunks: refers to the aggregation of physical links into larger, logical links.
Transmission Control Protocol (TCP): It is a library of routines that applications can use when they need reliable network communications with another computer. TCP is responsible for verifying the correct delivery of data from client to server. It adds support to detect errors or lost data and to trigger reconstruction until the data is correctly and completely received.
Internet Protocol (IP): A library of routines that TCP calls on, but which is also available to applications that do not use TCP. IP is responsible for transporting packets of data from node to node. It forwards each packet based on a four-byte destination address (the IP number).
The traffic on the Internet is growing very fast and soon the traffic rates needed between router pairs will be higher than the serial link transmission technology available. Currently, the highest transmission rate is 9.6 Gb/s, (on a single wavelength) but 2.4 Gb/s is much more commonly available. Purchasers of routers are already demanding 2.4 Gb/s links and it is expected that within a short time, some routes will need multiple physical links.
There are other reasons why multi-link routes are attractive. In situations where routers are clustered in close physical proximity, the use of multiple links might allow the interconnect to be multiple low cost links rather than single high cost connections. Another reason is that the application of the multi-link approach might also be a fast way to provide higher rate ports on existing routers. Yet another reason is that the use of multiple links allows more granularity of growth than the large stops in the transmission network and so may allow savings in bandwidth costs. Finally, another reason is that multiple links can allow for redundancy to cover link failure without requiring the spare link to cover the whole bandwidth of the route.
When using multiple links between two routers, it is a requirement that the total bandwidth be used efficiently. That is to say, the traffic offered must be spread over all available links. This is called load balancing. It would not be acceptable to have one link under utilized while traffic is queued on another. This suggests that packets from any source can be delivered over any link to any destination. In fact, because of the bursting nature of the traffic, allocating links statically to particular sources or destinations would result in inefficient use of the total available bandwidth.
When traffic streams are spread over multiple links, successive packets from a particular flow (for example, a TCP connection between two IP hosts) can travel over different lengths and may arrive at the destination out of order. The variability of delay can be caused by different path lengths or different congestion levels on the paths as well as the normal indeterminacy introduced by queuing and scheduling. The TCP can accommodate some misordering of packets, but there is a problem if too much misordering occurs on a connection where the transmitter is using the fast retransmission protocol. Typically, if a packet stream of A, B, C, D gets misordered such that the destination sees A, C, D, B, then the sender may assume that B was lost when it sees the third acknowledgement for A and will retransmit B. Occasional unnecessary retransmissions are not a problem, but a systematic misordering of packets for very many connections would result in a large drop in the throughput of the network, hence misuse of bandwidth.
Other existing or future applications, or transport protocols may also suffer from packet misordering but the TCP example is the most visible at present.
One of the current solutions to the problems outlined above is to provide multiple routers or additional ports on routers. However, this solution has a serious impact on the efficiency of routing methods used to build routing tables. In fact, more routes to a destination is a less desirable solution than one bigger route.
A load balancing technique, which does not cause packet miss-ordering, has been discussed and is called "Stream Based Load Balancing". In general, the methods rely on choosing a particular link for a traffic stream and using only that link for all its traffic A traffic stream is usually identified by the IP header (source address or source and destination address) and a hash function is used as a quick way to record and retrieve the link designated for traffic with a particular header.
Such methods can distribute traffic streams among links, but there is no prior knowledge of the rate or duration of the stream and, therefore, loads can be distributed quite unfairly. In some cases, a source address can be that of a proxy server which acts on behalf of many host machines and, in other cases, a destination address might be that of a large server which is accessed constantly by a number of source addresses.
Thus, there is a need in the industry to provide a method and a system capable of effecting low cost data traffic unit re-ordering in a network.